package 算法基础模板.chapter_01;

import java.util.*;

/**
 * 高精度计算
 *
 * @author Summerday
 */
public class HighPrecisionTemplate {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String A = scanner.nextLine();
        String B = scanner.nextLine();
        HighPrecisionTemplate t = new HighPrecisionTemplate();
        String add_res = t.doADD(A, B);
        System.out.println(add_res);
        System.out.println("--------------------");
        String sub_res = t.doSUB(A, B);
        System.out.println(sub_res);
        System.out.println("--------------------");
        String mul_res = t.doMUL(A, B);
        System.out.println(mul_res);
        System.out.println("--------------------");
        String div_res = t.doDIV(A, B);
        System.out.println(div_res);
    }

    public String doADD(String A, String B) {
        List<Integer> a = transferString2List(A);
        List<Integer> b = transferString2List(B);
        List<Integer> res = add(a, b);
        return transferList2String(res);
    }


    public String doSUB(String A, String B) {
        List<Integer> a = transferString2List(A);
        List<Integer> b = transferString2List(B);
        boolean f = false;
        List<Integer> res;
        if (cmp(a, b)) {
            res = sub(a, b);
        } else {
            f = true;
            res = sub(b, a);
        }
        String s = transferList2String(res);
        return f ? "-" + s : s;
    }

    public String doMUL(String A, String B) {
        List<Integer> a = transferString2List(A);
        int b = Integer.parseInt(B);
        List<Integer> res = mul(a, b);
        return transferList2String(res);
    }

    public String doDIV(String A, String B) {
        List<Integer> a = transferString2List(A);
        int b = Integer.parseInt(B);
        List<Integer> res = div(a, b);
        return transferList2String(res);
    }

    /**
     * 高精度加法 , 用数组表示每一位数
     * len(a) > len(b)
     */
    List<Integer> add(List<Integer> a, List<Integer> b) {
        if (a.size() < b.size()) return add(b, a);
        List<Integer> res = new ArrayList<>();
        int t = 0; // 进位
        for (int i = 0; i < a.size(); i++) {
            t += a.get(i);
            if (i < b.size()) t += b.get(i);
            res.add(t % 10);
            t /= 10;
        }
        if (t > 0) res.add(t);
        return res;
    }

    /**
     * 高精度减法, 前提需要 a >= b
     */
    List<Integer> sub(List<Integer> a, List<Integer> b) {
        List<Integer> res = new LinkedList<>();
        for (int i = 0, t = 0; i < a.size(); i++) {
            t = a.get(i) - t;
            if (i < b.size()) t -= b.get(i);
            res.add((t + 10) % 10);
            t = t < 0 ? 1 : 0;
        }
        // 移除前导零
        while (res.size() > 1 && res.get(res.size() - 1) == 0)
            res.remove(res.size() - 1);
        return res;
    }

    /**
     * 高精度 乘法  高位数*int类型数
     */
    List<Integer> mul(List<Integer> a, int b) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0, t = 0; i < a.size() || t > 0; i++) {
            if (i < a.size()) t += a.get(i) * b;
            res.add(t % 10);
            t /= 10;
        }
        while (res.size() > 1 && res.get(res.size() - 1) == 0)
            res.remove(res.size() - 1);
        return res;
    }

    /**
     * 高精度 除法  高位数/int类型数
     */
    List<Integer> div(List<Integer> a, int b) {
        List<Integer> res = new ArrayList<>();
        int r = 0;
        for (int i = a.size() - 1; i >= 0; i--) {
            r = r * 10 + a.get(i);
            res.add(r / b);
            r %= b;
        }
        Collections.reverse(res);
        while (res.size() > 1 && res.get(res.size() - 1) == 0)
            res.remove(res.size() - 1);
        return res;
    }


    // 判断 a >= b, a >= 0 , b>=0
    private boolean cmp(List<Integer> a, List<Integer> b) {
        if (a.size() != b.size()) return a.size() > b.size();
        for (int i = a.size() - 1; i >= 0; i--) {
            if (!a.get(i).equals(b.get(i))) return a.get(i) > b.get(i);
        }
        return true;
    }

    // 将字符串转化为 数组存储
    private List<Integer> transferString2List(String num) {
        List<Integer> res = new ArrayList<>();
        for (int i = num.length() - 1; i >= 0; i--) {
            res.add(num.charAt(i) - '0');
        }
        return res;
    }

    // 将数组转化为 字符串
    private String transferList2String(List<Integer> res) {
        StringBuilder sb = new StringBuilder();
        for (int i = res.size() - 1; i >= 0; i--) sb.append(res.get(i));
        return sb.toString();
    }
}
